package com.c2b.algorithm.leetcode.base;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author c2b
 * @since 2024/3/4 13:22
 */
public class LC2368 {
    static class Solution {

        public int reachableNodes(int n, int[][] edges, int[] restricted) {
            // 用布尔数组记录哪些节点是受限的。
            boolean[] isRestricted = new boolean[n];
            for (int i : restricted) {
                isRestricted[i] = true;
            }
            // 建树，只有当两个节点都不是受限的（都不在哈希集合中）才连边

            List<Integer>[] g = new List[n];
            for (int i = 0; i < n; i++) {
                g[i] = new ArrayList<>();
            }
            for (int[] v : edges) {
                if (isRestricted[v[0]] || isRestricted[v[1]]) {
                    continue;
                }
                g[v[0]].add(v[1]);
                g[v[1]].add(v[0]);
            }
            //Map<Integer, List<Integer>> map = new HashMap<>();
            //for (int[] e : edges) {
            //    int x = e[0];
            //    int y = e[1];
            //    if (isRestricted[x] || isRestricted[y]) {
            //        continue;
            //    }
            //    List<Integer> listX = map.getOrDefault(x, new ArrayList<>());
            //    listX.add(y);
            //    map.put(x, listX);
            //
            //    List<Integer> listY = map.getOrDefault(y, new ArrayList<>());
            //    listY.add(x);
            //    map.put(y, listY);
            //}
            // 从 0 出发 DFS 这棵树，统计能访问到的节点个数。
            Set<Integer> visited = new HashSet<>();
            //dfs(0, map, visited);
            dfs(0, g, visited);

            return visited.size();
        }

        private void dfs(int x, List<Integer>[] g, Set<Integer> visited) {
            if (visited.contains(x)) {
                return;
            }
            visited.add(x);
            for (Integer y : g[x]) {
                dfs(y, g, visited);
            }
        }

        //private void dfs(int x, Map<Integer, List<Integer>> map, Set<Integer> visited) {
        //    if (visited.contains(x)) {
        //        return;
        //    }
        //    visited.add(x);
        //    for (Integer y : map.get(x)) {
        //        dfs(y, map, visited);
        //    }
        //}
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.reachableNodes(7, new int[][]{{0, 1}, {1, 2}, {3, 1}, {4, 0}, {0, 5}, {5, 6}}, new int[]{4, 5}));
        System.out.println(solution.reachableNodes(7, new int[][]{{0, 1}, {0, 2}, {0, 5}, {0, 4}, {3, 2}, {6, 5}}, new int[]{4, 2, 1}));
    }
}
